#include	<stdlib.h>

typedef struct tnode* Tptr;
typedef struct tnode
{
    char splitchar;
    Tptr loch, eqch, hich;
}Tnode;

Tptr rsearch(Tptr root, const char *s)
{
    if (root == NULL)
        return NULL;
    Tptr child;

    if (*s == root->splitchar && *s == '\0')
        return root;
    else if (*s == root->splitchar) {
        child = root->eqch;
        ++s;
    }
    else if (*s < root->splitchar)
        child = root->loch;
    else 
        child = root->hich;
    child = rsearch(child, s);
    if (child) return root;
    return NULL;
}

int search(Tptr root, const char *s)
{
    Tptr p = root;
    while (p != NULL) 
    {
        if (*s < p->splitchar)
            p = p->loch;
        else if (*s > p->splitchar)
            p = p->hich;
        else {
            if (*s++ == '\0')
                return 1;
            p = p->eqch;
        }
    }
    return 0;
}

Tptr insert1(Tptr p, const char *s)
{
    if (p == NULL) {
        p = calloc(1, sizeof(Tnode));
        p->splitchar = *s;
        p->loch = p->hich = p->eqch = NULL;
    }
    if (*s < p->splitchar)
        insert1(p->loch, s);
    else if (*s > p->splitchar)
        insert1(p->hich, s);
    else {
        if (*s != '\0')
            insert1(p->eqch, s+1);
    }
}
